#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5, MOD=1e9;
ll n, k, s[N], a[N];
int main(){
    cin >> n >> k;
    for (int i=1; i<=k; i++){
        a[i] = 1;
        s[i] = s[i-1] + a[i];
    }
    for (int i=k+1; i<=n+1; i++){
        a[i] = (s[i-1] + MOD - s[i-k-1]) % MOD;
        s[i] = (s[i-1]%MOD + a[i]) % MOD;
    }
    cout << a[n+1];
    return 0;
}